package com.hjr.leetcode.question100;

/**
 * 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的 回文 子串。
 */
public class q5 {

    public static void main(String[] args) {
        // 这种需要退步的算法，一般可以使用动态规划，或者双指针
        System.out.println(longestPalindrome("cbbd"));
    }

    static int left = 0;
    static int right = 0;
    static int maxLength = 0;

    // 双指针
    public static String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            extend(s, i, i, maxLength);
            extend(s, i, i + 1, maxLength);
        }
        return s.substring(left, maxLength);
    }

    static void extend(String s, int left, int right, int n){
        //判断是否为回文
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            left--;
            right++;
        }
        if (n < right - left){
            maxLength = right - left;
            q5.left = left + 1;
            q5.right = right;
        }
    }

}
